package com.fwpsl.sort;

import java.util.Arrays;

/**
 * @author: 风戏fw
 * @date: 2024/2/28
 * @description: 堆排序（Heap Sort）是一种基于比较的排序算法，它的时间复杂度为O(nlogn)，其中n是待排序的元素数量。
 * 堆排序利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，
 * 并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
 * <p>
 * 堆排序的基本步骤包括：
 * 1. 建堆：将待排序的序列构造成一个大顶堆（或小顶堆）。此时，整个序列的最大值（或最小值）就是堆顶的根节点。
 * 2. 交换堆顶与末尾元素：将此时堆顶的元素（已经最大或最小）与末尾元素交换，此时末尾就为最大值。然后将剩余n-1个序列重新构造成一个堆，
 * 这样会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。
 * <p>
 * 具体实现时，可以使用数组来表示堆，数组的下标从0开始。对于给定下标i的元素，其左子节点下标为2i+1，右子节点下标为2i+2，
 * 其父节点下标为(i-1)/2（向下取整）。
 */
public class HeadSort {

    /**
     * 堆排序
     */
    public static int[] headSort(int[] arr) {
        int n = arr.length;
        //构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, i, n);
        }

        //进行堆排序
        for (int i = n - 1; i >= 1; i--) {
            // 把堆顶元素与最后一个元素交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            // 把打乱的堆进行调整，恢复堆的特性
            heapify(arr, 0, i);
        }
        return arr;
    }

    /**
     * 调整堆, 在当前节点及其子节点中，找到最大（最小值），放在该节点。
     */
    public static void heapify(int[] arr, int parent, int n) {
        //临时保存要下沉的元素
        int temp = arr[parent];
        //定位左孩子节点的位置
        int child = 2 * parent + 1;
        //开始下沉
        while (child < n) {
            // 如果右孩子节点比左孩子大，则定位到右孩子
            if (child + 1 < n && arr[child] < arr[child + 1]) {
                child++;
            }
            // 如果孩子节点小于或等于父节点，则下沉结束
            if (arr[child] <= temp) {
                break;
            }
            // 父节点进行下沉
            arr[parent] = arr[child];
            parent = child;
            child = 2 * parent + 1;
        }
        arr[parent] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {20, 30, 90, 40, 70, 110, 60, 10, 100, 50, 80};
        System.out.println("before sort:" + Arrays.toString(arr));

        // 升序排列
        headSort(arr);

        System.out.println("after sort:" + Arrays.toString(arr));
    }
}
